//如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数
//值排序之后中间两个数的平均值。 
//
// 例如， 
//
// [2,3,4] 的中位数是 3 
//
// [2,3] 的中位数是 (2 + 3) / 2 = 2.5 
//
// 设计一个支持以下两种操作的数据结构： 
//
// 
// void addNum(int num) - 从数据流中添加一个整数到数据结构中。 
// double findMedian() - 返回目前所有元素的中位数。 
// 
//
// 示例 1： 
//
// 输入：
//["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
//[[],[1],[2],[],[3],[]]
//输出：[null,null,null,1.50000,null,2.00000]
// 
//
// 示例 2： 
//
// 输入：
//["MedianFinder","addNum","findMedian","addNum","findMedian"]
//[[],[2],[],[3],[]]
//输出：[null,null,2.00000,null,2.50000] 
//
// 
//
// 限制： 
//
// 
// 最多会对 addNum、findMedian 进行 50000 次调用。 
// 
//
// 注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-
//stream/ 
// Related Topics 设计 双指针 数据流 排序 堆（优先队列） 👍 240 👎 0

package com.cute.leetcode.editor.cn;

import java.util.PriorityQueue;

public class ShuJuLiuZhongDeZhongWeiShuLcof {
    public static void main(String[] args) {
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class MedianFinder {
        /**
         * 参考剑指Offer上的题解，使用一个大顶堆和一个小顶堆分别保存两部分的数据
         * 两部分的数据并不需要排序，只需要知道左边的最大值以及右边的最小值即可
         * 保证左边的数据均小于右边的数据
         * 大顶堆保存左侧的数据，小顶堆保存右侧的数据
         * 小顶堆中的数据均要大于大顶堆的数据
         */
        PriorityQueue<Integer> left;
        PriorityQueue<Integer> right;
        int count;
        public MedianFinder() {
            left = new PriorityQueue<>((a, b) -> (b - a));
            right = new PriorityQueue<>();
        }

        /**
         * 插入规则如下：
         *  最大堆和最小堆间元素的差值数不能超过1
         *  当前两堆元素总数为偶数时，插入小顶堆（即右侧）
         *      为了保证小顶堆的元素均 > 大顶堆的元素，如果偶数时的num比大顶堆最大值要小
         *      需要先将其插入大顶堆，再将大顶堆顶部元素取出并插入小顶堆
         *      也可以直接先插入到另一边，再取回来
         *  奇数时同理
         */
        public void addNum(int num) {
            //简化的添加，去掉了判断条件
            if ((count & 1) == 1){
                right.add(num);
                left.add(right.poll());
            }else {
                left.add(num);
                right.add(left.poll());
            }
            /*if ((count & 1) == 0){ //偶数
                if (left.size() > 0 && num < left.peek()){
                    left.add(num);
                    right.add(left.poll());
                }else right.add(num);
            }else {// 奇数
                if (right.size() > 0 && num > right.peek()){
                    right.add(num);
                    left.add(right.poll());
                }else left.add(num);
            }*/
            count++;
        }
        public double findMedian() {
           return (count & 1) == 1 ? right.peek() : (left.peek() + right.peek()) / 2.0;
        }
    }

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
//leetcode submit region end(Prohibit modification and deletion)

}